summary:Let $A_n$ $(n \geq 1)$ be the set of all integers $x$ such that there exists a connected graph on $n$ vertices with precisely $x$ spanning trees. It was shown by Sedláček that $|A_n|$ grows faster than the linear function. In this paper, we show that $|A_{n}|$ grows faster than $\sqrt {n} {\rm e}^{({2\pi }/{\sqrt 3})\sqrt {n/\log {n}}}$ by making use of some asymptotic results for prime partitions. The result settles a question posed in J. Sedláček, On the number of spanning trees of finite graphs, Čas. Pěst. Mat., 94 (1969), 217–221.
展开▼
